package com.milo.algorithm.sort;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

/**
 * @author: Milogenius
 * @create: 2019-07-05 11:13
 * @description: 演示希尔排序
 * <p>
 *
 *  一.基本思想
 *  希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
 *  待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
 *
 *
 *  二.算法步骤
 * 1.选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
 * 2.按增量序列个数 k，对序列进行 k 趟排序；
 * 3.每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。
 *   仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 *
 * </p>
 **/
public class ShellSort {

    public int[] sort(int[] sourceArray){
        //对array进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        int grap = 1;
        while (grap < arr.length){
            grap = grap * 3 + 1;
        }
        while (grap>0){
            for (int i = grap; i <arr.length ; i++) {
                int tmp = arr[i];
                int j = i - grap;
                while (j >= 0 && arr[j] >tmp){
                    arr[j + grap] = arr[j];
                    j -= grap;
                }
                arr[j+grap] = tmp;
            }
            grap = (int)Math.floor(grap / 3);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3,44,38,5,47};
        ShellSort shellSort = new ShellSort();
        int[] sort = shellSort.sort(arr);
        System.out.println("排序后的数组顺序:"+ JSON.toJSONString(sort));
    }
}
